#tarjan 系列算法

snippet tarjan_qlt "tarjan-强连通分量" b
// ========== tarjan 求强连通分量
namespace Tarjan_QLT {
    int dfn[maxn],low[maxn],color[maxn];
    bool instack[maxn];
    int idx,color_cnt;
    std::stack<int> sta;
    void qlt_init(){
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(instack,0,sizeof(instack));
        color_cnt = idx = 0;
    }
    void tarjan(int u){ 
        dfn[u] = low[u] = ++idx; //时序编号
        sta.push(u);			 //入栈
        instack[u] = 1;
        int i;
        for( i =head[u]; ~i ;i = e[i].next){
            int &v = e[i].v;
            if( !dfn[v]){ //没有访问过
                tarjan(v);
                low[u] = std::min(low[u],low[v]); //<u,v> 是树边
            }
            else if( instack[v]){ //已经访问,且未输出
                low[u] = std::min(low[u],dfn[v]);
            }
        }

        //强连通分量子树的跟
        if( dfn[u] == low[u]){
            color_cnt++;
            int t = -1;
            do {
                t = sta.top(); sta.pop();
                instack[t] = 0;
                color[t] = color_cnt;
            }
            while( t != u);
        }
    }
    void work(int n){
        for( int i =1;i<=n;i++){ //从每个点开始
            if( !dfn[i]) tarjan(i);
        }
    }
}
// ========== tarjan 求强连通分量 END
endsnippet

snippet udg_tarjan_cut_node "割点" b
//TODO
endsnippet

snippet udg_tarjan_bridge "割边" b
//TODO
endsnippet

snippet udg_tarjan_e_bcc "边双" b
//TODO
endsnippet

snippet udg_tarjan_n_bcc "点双" b
//TODO
endsnippet

snippet udg_tarjan "割点，割边，点双，边双4合1 tarjan" b
// ==== 此模板可以求无向图割点,割边,边分,点双
#define CUT_N  //割点 开关
#define BRIDGE //割边 开关
#define N_BCC  //点双 开关
#define E_BCC  //边双 开关
//不用加instack
namespace UDG_tarjan {
    using namespace xlx1; // 从0开始存边
    typedef long long ll;
    int low[maxn],dfn[maxn];
    int index=0,bridge= 0,child=0,root,t=-1;

#ifdef CUT_N
    bool cut_n[maxn];   //点是否割点
#endif

#ifdef BRIDGE
    bool cut_e[maxe];   //边是否割边
#endif

#ifdef E_BCC
    int color_n[maxn],color_n_cnt=0;  //边双 给点染色
    stack<int> sta_e;   //边双 存点入栈
#endif

#ifdef N_BCC
    stack<int> sta_n;   //存边的栈
    int color_e_cnt=0,color_e[maxe]; //对边进行染色
    int color_n_t[maxn]; //临时
    int nbcc_cnt=0; //点双计数
    vector<int> nbcc_v[maxn];
#endif

    void udg_tarjan_init(int Root = 1){
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        index=bridge=0;
#ifdef CUT_N
        memset(cut_n,0,sizeof(cut_n));
        root = Root,child=0;
#endif
#ifdef BRIDGE
        memset(cut_e,0,sizeof(cut_e));
#endif
#ifdef E_BCC
        memset(color_n,0,sizeof(color_n));
        color_n_cnt = 0; //sta_e.clear();
#endif
#ifdef N_BCC
        color_e_cnt=nbcc_cnt=0;
        memset(color_e,0,sizeof(color_e));
        memset(color_n_t,0,sizeof(color_n_t));
        //for (const auto& e : nbcc_v) e.clear();
#endif
    }

    void tarjan(int u,int E){
        low[u] = dfn[u] = ++index; 
#ifdef E_BCC
        sta_e.push(u); //边双 存点入栈
#endif
        for(int i= head[u]; ~i ;i=e[i].next){
            int v = e[i].v;
            if( !dfn[v]){
#ifdef N_BCC
                sta_n.push(i); //点双 存边入栈
#endif
#ifdef CUT_N
                if( u == root) child++;   //割点 根点孩子加1
#endif
                tarjan(v,i);
                if( low[u] > low[v]) low[u] = low[v];
#ifdef BRIDGE   // 割边
                if( low[v] > dfn[u]){ bridge++; cut_e[i]= cut_e[i^1] = 1; }
#endif
#ifdef CUT_N    // 割点
                if( low[v] >= dfn[u] && u != root) cut_n[u] = 1;
#endif
#ifdef N_BCC
                //点双 对边进行染色
                if( low[v] >=dfn[u] ){
                    nbcc_cnt++;
                    t=-1; do {
                        t = sta_n.top();sta_n.pop();
                        color_e[t] = color_e[t^1] = color_e_cnt;
                        int u = e[t].u,v = e[t].v; //核心思想：不重复的放入
                        if( color_n_t[u] != nbcc_cnt){
                            nbcc_v[nbcc_cnt].push_back(u);
                            color_n_t[u] = nbcc_cnt;
                        }
                        if( color_n_t[v] != nbcc_cnt) {
                            nbcc_v[nbcc_cnt].push_back(v);
                            color_n_t[v] = nbcc_cnt;
                        }
                    }while( t != i );
                }
#endif
            }
            else if( (i^1) != E && low[u] > dfn[v]) low[u] = dfn[v];
        }
#ifdef CUT_N // 割点
        if( u == root && child>1) cut_n[u] = 1;
#endif
#ifdef E_BCC // 边双
        if( low[u] == dfn[u]){
            color_n_cnt++,t=-1;
            do {
                t = sta_e.top();sta_e.pop();
                color_n[t] = color_n_cnt;
            }while( t != u);
        }
#endif
    }
}
endsnippet
